L'algorithme de Robison-Schensted se base sur le fait que le résultat de l'algorithme patience sorting contient trop d'informations, car seuls les premiers nombres de chaque colonne nous intéresse dans ce tableau (car, à chaque étape, eux seuls interviennent dans le choix d'ouvrir une nouvelle colonne ou non)
(Permutation, Patience sorting)
Algorithme
L'algorithme de Robinson-Schensted fonctionne de la même manière que le patience sorting, saufqu'au lieu de pousser toute une colonne, un nombre peut en pousser un autre sur la deuxième ligne, qui cherche alors lui aussi sur quelle colonne se placer, etc récursivement
En parallèle du premier tableau renvoyé par l'algorithme de Robinson-Schensted, on peut créer un tableau dont chaque case est occupée par le nombre \(k\) si elle a été occupée pour la première fois lors de la \(k\)ème étape de l'algorithme
On appelle tableau d'enregistrement un tel tableau
L'algorithme de Robinson-Schensted associe à une permutation \(\sigma\) le triplet \((\lambda,P,Q)\), avec...
Algorithme appliqué à la permutation \((4,1,2,7,6,5,8,9,3)\) :
Vocabulaire
[algorithme de Robinson-Schensted]
On appelle étape d'insertion le cycle consistant à ajouter une nouvelle valeur au tableau et la cascade résultante de nombres poussés
[algorithme de Robinson-Schensted]
On peut défaire une étape d'insertion en poussant un nombre hors du tableau. Il n'y a qu'une seule cascade de nombres possible à ce moment là.
Cette opération est appelée étape de suppression
Intérêt
Proposition :
Un tableau résultant de l'algorithme de Robsinon-Schensted a ses nombres disposés dans l'ordre croissant sur chaque ligne et chaque colonne du tableau d'insertion. De plus, la taille de la première ligne est égale à la taille de la plus grande sous-suite croissante de \(\sigma\)